from typing import List

"""
45. 跳跃游戏 II
https://leetcode.cn/problems/jump-game-ii/description/?envType=study-plan-v2&envId=top-interview-150
"""


class Solution:
    """
    力扣官方题解
    """

    def jump2(self, nums: List[int]) -> int:
        n = len(nums)
        maxPos, end, step = 0, 0, 0
        for i in range(n - 1):
            # 贪心：选择当前位置能够跳的最远位置
            if maxPos >= i:
                # 更新 maxPos
                maxPos = max(maxPos, i + nums[i])
                # 若到了 end, 说明已经到最远位置了, 需要更新 end 和 step
                if i == end:
                    end = maxPos
                    step += 1
        return step

    def jump(self, nums: List[int]) -> int:
        # for i in range(len(nums)):
        if len(nums) == 1:
            return 0
        i, step, l, maxJump = 0, 0, 0, 0
        while i <= len(nums) :
            step += 1
            # 若下一步能跳到最后一个下标, 则返回
            if i >= len(nums) - 1 or nums[i] >= len(nums) - 1:
                return step
            # 看下一步能跳到的所有下标, 取最大
            l = nums[i] + i
            # 下一步能跳到最远的地方
            maxJump = self.maxJump(nums[i:l + 1])
            i += maxJump

        return step

    """
    当前位置能跳到的最远位置
    """

    def maxJump(self, nums: List[int]) -> int:
        maxI = 0
        for i in range(len(nums)):
            maxI = max(maxI, i + nums[i])
        return maxI


if __name__ == '__main__':
    s = Solution()
    # print(s.jump([4, 3, 1, 1, 2, 1, 2]))
    # print(s.jump([2, 3, 1, 1, 4]))
    # print(s.jump([2, 2, 0, 1, 4]))
    # print(s.jump([0]))
    # print(s.jump([1,0]))
    # print(s.jump([3, 2, 1]))
    print(s.jump2([1, 2, 1, 1, 1]))
